package org.algorithm.熊猫.数组.三月.第三周;

import java.util.Arrays;

/**
 * @version 1.0
 * @date 2022/03/16 9:08 PM
 * @description: url: https://leetcode-cn.com/problems/frequency-of-the-most-frequent-element/
 */
public class 最高频元素的频数 {

    public static void main(String[] args) {
        int[] nums = {1, 4, 8, 13};
        System.out.println(maxFrequency(nums, 11));
    }

    public static int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        long sum = 0;
        int l = 0, result = 1;
        //区间  l - i 进行差值累加判断，当差值在k范围内， 最大频数为i-l,  将区间l，i 进行滑动判断到最后。
        for (int i = 1; i < n; i++) {
            sum += (long) (nums[i] - nums[i - 1]) * (i - l);
            while (sum > k) {
                sum -= nums[i] - nums[l];
                ++l;
            }
            result = Math.max(result, i - l + 1);
        }
        return result;
    }
}
